翻訳と辞書 Words near each other ・ Sorsum ・ Sorsçay ・ Sort ・ Sort (C++) ・ SORT (journal) ・ Sort (typesetting) ・ Sort (Unix) ・ Sort code ・ Sort Merge Generator ・ Sort Of ・ Sort of Revolution ・ Sort Sol ・ Sort sol ・ Sort, Lleida ・ Sort-en-Chalosse ・ Sort-merge join ・ Sorta ・ Sorta (band) ・ Sortable list of islands of Western Australia ・ Sortal ・ Sortase ・ Sortase A ・ Sortase B ・ Sortavala ・ Sorte Ellen og hendes søn ・ Sorte Hest ・ Sorte Nula ・ Sorteberg relay ・ Sorted ・ Sorted (film) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Sort-merge join ： ウィキペディア英語版 Sort-merge join The sort-merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the Sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time. In practice, the most expensive part of performing a sort-merge join is arranging for both inputs to the algorithm to be presented in sorted order. This can be achieved via an explicit sort operation (often an external sort), or by taking advantage of a pre-existing ordering in one or both of the join relations. The latter condition can occur because an input to the join might be produced by an index scan of a tree-based index, another merge join, or some other plan operator that happens to produce output sorted on an appropriate key. Let's say that we have two relations $R$ and $S$ and . $R$ fits in $P\_$ pages memory and $S$ fits in $P\_$ pages memory. So, in the worst case Sort-Merge Join will run in $O(P\_+P\_)$ I/Os. In the case that $R$ and $S$ are not ordered the worst case time cost will contain additional terms of sorting time: $O(P\_+P\_+P\_\backslash log(P\_)+\; P\_\backslash log(P\_))$, which equals $O(P\_\backslash log(P\_)+\; P\_\backslash log(P\_))$ (as linearithmic terms outweigh the linear terms, see Big O notation – Orders of common functions). ==Pseudocode== For simplicity, the algorithm is described in the case of an inner join of two relations on a single attribute. Generalization to other join types, more relations and more keys is straightforward. function sortMerge(relation left, relation right, attribute a) var relation output var list left_sorted := sort(left, a) ''// Relation left sorted on attribute a'' var list right_sorted := sort(right, a) var attribute left_key, right_key var set left_subset, right_subset ''// These sets discarded except where join predicate is satisfied'' advance(left_subset, left_sorted, left_key, a) advance(right_subset, right_sorted, right_key, a) while not empty(left_subset) and not empty(right_subset) if left_key = right_key ''// Join predicate satisfied'' add cartesian product of left_subset and right_subset to output advance(left_subset, left_sorted, left_key, a) advance(right_subset, right_sorted, right_key, a) else if left_key < right_key advance(left_subset, left_sorted, left_key, a) else ''// left_key > right_key'' advance(right_subset, right_sorted, right_key, a) return output ''// Remove tuples from sorted to subset until the sorted().a value changes'' function advance(subset out, sorted inout, key out, a in) key := sorted().a subset := emptySet while not empty(sorted) and sorted().a = key insert sorted() into subset remove sorted() 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sort-merge join」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.